GA is one of the evolutionary algorithms that mimics the process of natural evolution and selection. Theoretically speaking, GA is a dynamical iterative process. During the iterative process, GA proceeds to initialize a population of solutions and then to improve it through recurrent application of genetic operators including selection, crossover, and mutation operator. Commonly, the algorithm terminates when either a maximum number of generations has been reached, or a satisfactory fitness level has been reached for the population.

Selection is one of the important operators existing in GA. In each generation, the fitness value of every individual in the population is evaluated. The individuals with high fitness value are stochastically selected from the current population and then form a new generation. Mutation represents the changes in gene of an individual. The role of mutation is to provide a guarantee that the search algorithm is not trapped at a local optimum.^[24]

Crossover operator inevitably involves generating new individuals for improving search efficiency in the solution space. Crossover operator is introduced for two individuals (parents), so that they can combine to produce two more individuals (children). In crossover operator, the inter-individual interactions in the population can be abstracted as complex networks, where the individuals can be represented by the vertices and the interactions among individuals can be denoted by the edges. Now that a crossover operator may be executed between any two individuals in the canonical GA, the interaction structure can be represented by a fully-connected topology.

Fig. 1.

	Figure Option ViewDownloadNew Window
	Fig. 1. The flow diagram of genetic algorithm.

In the diagram of Fig. 2, how an offspring generated from their parents in single-point crossover is described.

Fig. 2.

	Figure Option ViewDownloadNew Window
	Fig. 2. Crossover operator.

The essence of genetic operators can be explained by the schema theorem proposed by Holland.^[24] In GA, a schema is propagated if individuals in the current generation match it and so do those in the next generation. Holland’s schema theorem demonstrated that short, low-order schemata with above-average fitness increase exponentially in successive generations. GA is a set of operations for schemata of chromosome in nature. The highly fit schemata are propagated to next generation through the selection operator. Then, the schemata are recombined by crossover operator. In mutation operator, the schemata are mutated to generate new schemata. In conclusion, the schemata evolve to higher fitness value in successive generations, which build the globally optimal solution.

A real-valued function set F = {f₁ (x), f₂ (x), …,f₁₅(x)} consisting of 15 well-known benchmark functions (f₁f₁₀,^[25]f₁₁f₁₅^[26]) is employed to illustrate the performance of t optimization algorithms. These 15 test functions are shown in Table 1.

Table 1.

Table 1.

Table 1. The flow diagram of genetic algorithm. . Function name Formula D Range[xminxmax] Optimum Unimodal Sphere 30 [−100, 100]D 0 Schwefel 2.22 30 [−10, 10]D 0 Schwefel 1.2 30 [−100, 100]D 0 Schwefel 2.21 f4 (x) = |xi| 30 [−100, 100]D 0 Generalized Rosenbrock 30 [−30, 30]D 0 Quaric 30 [−1.28, 1.28]D 0 Multimodal Generalized Rastrigin 30 [−5.12, 5.12]D 0 Generalized Griewank 30 [−600, 600]D 0 Generalized Schwefel 2.26 30 [−500, 500]D −418.983D Ackley 30 [−30, 30]D 0 Modified Schwefel 30 [−100, 100]D 0 HappyCat 30 [−100, 100]D 0 HGBat 30 [−100, 100] D 0 Griewank plus Rosenbrock f14 (x) = f8 (f5 (x1,x2)) + f8 (f5 (x2,x3)) +⋯+ f8 (f5(xD−1,xD)) + f8 (f5 (xD,x1)) 30 [−100, 100] D 0 Scaffer F6 f15 (x) = g(x1, x2) + g(x2,x3) + ⋯ + g (xD−1,xD) + g (xD,x1) 30 [−100, 100] D 0

Table 1. The flow diagram of genetic algorithm. .

The first six functions are unimodal functions, and the next nine functions are multimodal functions designed with a considerable amount of local minima. All test functions are tested with the dimension of 30. Stimulations are carried out to find the global minimum of each function.

In previously established GAs, the interaction structure is assumed to be a fully-connected topology. It is possible that a crossover operator can be executed between any two individuals in a population. However, the information dissemination velocity depends on the network density, e.g., in the fully-connected topology, each individual’s information can be quickly transferred to all other individuals which may cause convergence rapidly with an unsatisfactory solution. Since it was demonstrated that the network structural properties play key roles in PSO algorithm, we are inspired to investigate the effects of various topologies on the performance of GA.

Holland’s schema theorem demonstrated that the schemata with high fitness increase exponentially in successive generations, which makes it possible for GA to search the global optimum. Hence, the crossover is the key operator in which short, low-order schemata with above-average fitness are recombined and find the global optimum in the end. We applied the network topology to represent the population interaction structure in GA. A schema matched by an individual represents the information of a vertex in the network. In crossover operator, the recombination of schemata can be abstracted as information dissemination among vertices in the network. The dissemination of schemata-matched global optimum in the network will improve the solution quality. However, the dissemination of schemata-matched local optimum will cause convergence with an unsatisfactory local optimum. Therefore, in a high-density topology, the information dissemination is too fast to escape from the local optimum. Moreover, the global optimum will be obtained more likely in a low-density topology, though it may impede convergence because of the slow dissemination of information. Hence we use the topologies from the ring to complete connection to test the algorithm performance variation of regular topologies with different network density represented by the average degree (Fig. 3).

In order to investigate the effect of network density, all the topologies above are tested in the framework of RC–GA^[11] for the optimization of 15 benchmark functions (Table 1). In RC–GA, the gene consists of real-valued object parameters, and the evolution operates on the natural representation, i.e., each gene is represented by a 64-bit floating point number. As the interaction between two individuals executed mainly on crossover operator, the regular topology is introduced in the step of crossover. The individuals represent the vertices in regular topologies with different network density. Figure 3 displays this feature more intuitively, e.g., in a nearest-neighbor coupled network shown in Fig. 3(b), each individual can crossover with one of 4 neighbors in the population. The modification is also carried out in selection operation, where the offspring’s positions in the network do not generate randomly as traditional GA but inherit their parents’ positions. Hence, the topologies are maintained in successive generations.

Fig. 3.

	Figure Option ViewDownloadNew Window
	Fig. 3. Networks with different density K (the average degree). The network density grows from left to right. (a) Ring-like network with K = 2. (b) Nearest-neighbor coupled network with K = 4. (c) nearest-neighbor coupled network with K = 6. (d) Fully-connected network.

For GA with different topologies, the size of population is set to 100, the probability of crossover and mutation is set to 0.8 and 0.01. Schaffer recommended the range of parameters in GA.^[27] Since the algorithms are stochastic, their performance on each test function is evaluated based on statistics obtained from 50 independent runs.

The quality of the averaged optimal fitness is shown in Table 2. The shaded cells in Table 2 indicate that the corresponding algorithm outperforms fully-connected GA (K = 100) for a particular function. It is obvious that the shaded cells occupy the most space of the table and concentrate in GAs with low-density topologies, which means that GAs with low-density topologies can obtain better optimal fitness for most of the functions. A value in italic bold indicates that the corresponding algorithm is the best on a particular test function. It can be observed that the fully-connected GA performs the best only for 2 unimodal function (f₂ and f₅), and the GA with ring network (K=2) performs the best for 6 functions. As shown in Table 2, neither the fully-connected topology nor ring topology performs the best for most of the test functions. The information dissemination of fully-connected network is too fast to be able to escape from the local optima, while the ring topology slows the information dissemination and impedes its convergence speed. Therefore, the results confirm the supposition above about the effect of the network density.

Table 2

Table 2

Table 2 Average and standard deviation of the best fitness found by GA with different network densities. .

Table 2 Average and standard deviation of the best fitness found by GA with different network densities. .

Theoretically speaking, GA finds the globally optimal solution by obtaining the balance between exploration and exploitation.^[28] We find that a low-density topology may benefit exploration while a high-density topology facilitates exploitation. Thus, a dynamic variation from ring network to fully-connected topology may trade off the exploration and exploitation throughout the optimization process, resulting in a good performance. Eiben analyzed adaptive parameter control methods in evolutionary algorithms.^[29,30] Srinivas proposed adaptive probabilities of crossover and mutation in genetic algorithms.^[12] They insisted that some form of feedback from the search process should be used to determine the direction and/or magnitude of the change to the strategy parameter.

In our algorithm, the network density is modified through the feedback of convergence degree from the search process. To vary network density dynamically, it is essential to identify whether the GA is converging to an optimum. The difference between the average and minimum fitness values, Δ = f̄ – f_min, is used as a yardstick for detecting the convergence degree of the GA. In addition, to improve the universality of the algorithm, Δ is normalized according to γ with Eq. (1)

For DT-GA, the population sizes are set to 100, the probabilities of crossover and mutation are set to 0.8 and 0.01 respectively. c is set to 50. For each test function, the algorithm executed 50 runs independently. All simulations are performed on a PC with 3.2 GHz CPU and 12 GB of RAM. All GAs are implemented in C++ language.

A summary of the results is presented in Table 3, where the shaded cells indicate that the corresponding algorithm outperforms the DT-GA on a particular test function. It can be observed that few test algorithms outperform DT-GA for the functions. In particular, compared to GA with a fully-connected network, DT-GA performs better for 13 test functions. The value in italic bold represents that the corresponding test algorithm performs the best. DT-GA performs the best for 6 test functions. The superiority of DT-GA is apparent. Thus, it is reasonable that DT-GA gives rise to a better balance between the convergence speed and the optimum quality.

Table 3.

Table 3.

Table 3. Average and standard deviation for the best fitness found by test GAs. .

Table 3. Average and standard deviation for the best fitness found by test GAs. .

The essence of the algorithm can be illustrated by Fig. 4 which shows the variation of minimum fitness value (f_min), convergence degree (γ) and network density (K) during search process.

Fig. 4.

	Figure Option ViewDownloadNew Window
	Fig. 4. Variation of fmin, γ, and K.

At the beginning of evolution, the network density is set to 2 considering the information dissemination of the ring network (K = 2) is so slow that GA has enough time to find a better optimum. When the convergence speed slows down, the convergence degree decreases and K increases inversely since a high-density network can speed up convergence. Therefore, the negative correlation between convergence degree and network density makes DT-GA trade off the exploration and exploitation throughout the optimization process